package com.yiwenup.struct._06_graph;

import com.yiwenup.struct._04_heap.BinaryHeap;
import com.yiwenup.struct._05_unionfind.GenericQuickUnion;
import com.yiwenup.struct._06_graph.base.AbstractGraph;
import com.yiwenup.struct._06_graph.base.Graph;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

/**
 * 邻接表实现
 **/
public class ListGraph<V, W> extends AbstractGraph<V, W> implements Graph<V, W> {

    private Map<V, Vertex> vertices = new HashMap<>();
    private Set<Edge> edges = new HashSet<>();
    private Comparator<Edge> edgeComparator = (Edge e1, Edge e2) -> weightManager.compare(e1.weight, e2.weight);

    public ListGraph() {
        super(null);
    }

    public ListGraph(WeightManager<W> weightManager) {
        super(weightManager);
    }

    @Override
    public int vertexSize() {
        return vertices.size();
    }

    @Override
    public int edgeSize() {
        return edges.size();
    }

    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v, new Vertex(v));
    }

    @Override
    public void addEdge(V from, V to) {
        this.addEdge(from, to, null);
    }

    @Override
    public void addEdge(V from, V to, W weight) {
        // 1、判断 from 和 to 的存在性，若不存在则进行创建
        Vertex fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex(from);
            vertices.put(from, fromVertex);
        }
        Vertex toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex(to);
            vertices.put(to, toVertex);
        }

        // 2、判断之前 from 到 to 是否已经有边了，有则只更新权值
        Edge edge = new Edge(fromVertex, toVertex);
        edge.weight = weight;

        // 先删再加
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

    @Override
    public void removeVertex(V v) {
        // 存在性校验，如果存在则删除节点
        Vertex vertex = vertices.remove(v);
        if (vertex == null) return;

        // 删除 V 关联的出度
        for (Iterator<Edge> iterator = vertex.outEdges.iterator(); iterator.hasNext(); ) {
            Edge outEdge = iterator.next();
            outEdge.to.inEdges.remove(outEdge);
            iterator.remove();
            edges.remove(outEdge);
        }
        // 删除 V 关联的入度
        for (Iterator<Edge> iterator = vertex.inEdges.iterator(); iterator.hasNext(); ) {
            Edge inEdge = iterator.next();
            inEdge.from.outEdges.remove(inEdge);
            iterator.remove();
            edges.remove(inEdge);
        }
    }

    @Override
    public void removeEdge(V from, V to) {
        // 顶点存在性校验
        Vertex fromVertex = vertices.get(from);
        Vertex toVertex = vertices.get(to);
        if (fromVertex == null || toVertex == null) {
            return;
        }

        // 删除
        Edge edge = new Edge(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

    @Override
    public void bfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;

        Vertex beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        Set<Vertex> visited = new HashSet<>();

        Queue<Vertex> queue = new LinkedList<>();
        queue.offer(beginVertex);
        visited.add(beginVertex);

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            // System.out.println(vertex);
            if (visitor.visit(vertex.value)) return;
            for (Edge outEdge : vertex.outEdges) {
                if (visited.contains(outEdge.to)) continue;
                queue.offer(outEdge.to);
                visited.add(outEdge.to);
            }
        }
    }

    @Override
    public void dfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;

        Vertex beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        HashSet<Vertex> visited = new HashSet<>();
        dfs(beginVertex, visited, visitor);
    }

    /**
     * 节点递归
     */
    private void dfs(Vertex vertex, HashSet<Vertex> visited, VertexVisitor<V> visitor) {
        // 递归方式
//        System.out.println(vertex);
//        visited.add(vertex);
//        for (Edge outEdge : vertex.outEdges) {
//            if (!visited.contains(outEdge.to)) {
//                dfs(outEdge.to, visited);
//            }
//        }

        // 非递归方式
        Stack<Vertex> stack = new Stack<>();
        // 初始化：起点入栈
        stack.push(vertex);
        visited.add(vertex);
        // System.out.println(vertex);
        if (visitor.visit(vertex.value)) return;

        while (!stack.isEmpty()) {
            // 每弹出一个定点时，就将其的边加入到栈中
            Vertex top = stack.pop();

            for (Edge outEdge : top.outEdges) {
                if (visited.contains(outEdge.to)) continue;

                stack.push(outEdge.from);
                stack.push(outEdge.to);
                visited.add(outEdge.to);
                // System.out.println(outEdge.to);
                if (visitor.visit(outEdge.to.value)) return;

                break;
            }
        }
    }

    @Override
    public List<V> topologiccalSort() {
        // 存放结果
        List<V> list = new ArrayList<>();
        // 存放入度为0的节点
        Queue<Vertex> queue = new LinkedList<>();
        // 维护节点的入度数值
        Map<Vertex, Integer> inDegree = new HashMap<>();

        // 初始化
        vertices.forEach((V v, Vertex vertex) -> {
            int inEdgeSize = vertex.inEdges.size();
            if (inEdgeSize == 0) {
                queue.offer(vertex);
            } else {
                inDegree.put(vertex, inEdgeSize);
            }
        });

        while (!queue.isEmpty()) {
            Vertex vertex = queue.poll();
            list.add(vertex.value);
            for (Edge outEdge : vertex.outEdges) {
                int in = inDegree.get(outEdge.to) - 1;
                if (in == 0) {
                    queue.offer(outEdge.to);
                } else {
                    inDegree.put(outEdge.to, in);
                }
            }
        }

        return list;
    }

    @Override
    public Set<EdgeInfo<V, W>> mst() {
        return this.kruskal();
    }

    /**
     * 最小生成树 - prim 算法
     */
    public Set<EdgeInfo<V, W>> prim() {
        // 随意取出一个顶点，从此处开始切分
        Iterator<Vertex> iterator = vertices.values().iterator();
        if (!iterator.hasNext()) return null;

        Set<EdgeInfo<V, W>> edgeInfos = new HashSet<>();
        Vertex beginVertex = iterator.next();
        Set<Vertex> addVertices = new HashSet<>();
        addVertices.add(beginVertex);

        // 使用小顶堆存放切边
        BinaryHeap<Edge> heap = new BinaryHeap<Edge>(beginVertex.outEdges, edgeComparator);

        int size = vertices.size() - 1;
        while (!heap.isEmpty() && edgeInfos.size() < size) {
            Edge edge = heap.remove();

            if (addVertices.contains(edge.to)) continue;

            addVertices.add(edge.to);
            edgeInfos.add(edge.info());
            heap.addAll(edge.to.outEdges);
        }

        return edgeInfos;
    }

    /**
     * 最小生成树 - kruskal 算法
     */
    public Set<EdgeInfo<V, W>> kruskal() {
        if (vertices.size() == 0) return null;

        Set<EdgeInfo<V, W>> edgeInfos = new HashSet<>();
        BinaryHeap<Edge> heap = new BinaryHeap<Edge>(edges, edgeComparator);
        GenericQuickUnion<Vertex> uf = new GenericQuickUnion<>();
        vertices.forEach((k, v) -> {
            uf.initSet(v);
        });

        int size = vertices.size() - 1;
        while (!heap.isEmpty() && edgeInfos.size() < size) {
            Edge edge = heap.remove();
            if (uf.isSame(edge.from, edge.to)) continue;

            edgeInfos.add(edge.info());
            uf.union(edge.from, edge.to);
        }

        return edgeInfos;
    }


    @Override
    public Map<V, W> shortestPath(V begin) {
        Vertex beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        // 被选中的路径
        Map<V, W> selectedPaths = new HashMap<>();
        Map<Vertex, W> paths = new HashMap<>();

        // 初始化paths
        for (Edge outEdge : beginVertex.outEdges) {
            paths.put(outEdge.to, outEdge.weight);
        }

        while (!paths.isEmpty()) {
            // 石子离开桌面
            Map.Entry<Vertex, W> minEntry = getMinPath(paths);
            // 置为选中的路径
            Vertex minVertex = minEntry.getKey();
            selectedPaths.put(minVertex.value, minEntry.getValue());
            // 移除
            paths.remove(minVertex);
            // 松弛操作
            for (Edge outEdge : minVertex.outEdges) {
                // 若outEdge.to已经离开桌面，则无需再进行松弛操作
                if (selectedPaths.containsKey(outEdge.to.value) || outEdge.to.equals(beginVertex)) continue;
                // 目前计算的最短路径
                W newWeight = weightManager.add(minEntry.getValue(), outEdge.weight);
                // 之前的最短路径
                W oldWeight = paths.get(outEdge.to);

                if (oldWeight == null || weightManager.compare(newWeight, oldWeight) > 0) {
                    paths.put(outEdge.to, newWeight);
                }
            }
        }
        return selectedPaths;
    }

    @Override
    public Map<V, PathInfo<V, W>> shortestPathInfo(V begin) {
        return dijkstra(begin);
    }

    /**
     * 迪杰斯特拉算法 - 求单源最短路径（不能存在负权边）
     *
     * @param begin 起始点
     * @return 路径信息
     */
    private Map<V, PathInfo<V, W>> dijkstra(V begin) {
        Vertex beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        // 被选中的路径
        Map<V, PathInfo<V, W>> selectedPaths = new HashMap<>();
        Map<Vertex, PathInfo<V, W>> paths = new HashMap<>();

        // 初始化paths
        for (Edge outEdge : beginVertex.outEdges) {
            PathInfo<V, W> pathInfo = new PathInfo<>();
            pathInfo.weight = outEdge.weight;
            pathInfo.edgeInfos.add(outEdge.info());
            paths.put(outEdge.to, pathInfo);
        }

        while (!paths.isEmpty()) {
            // 石子离开桌面
            Map.Entry<Vertex, PathInfo<V, W>> minEntry = getMinPathInfo(paths);
            // 置为选中的路径
            Vertex minVertex = minEntry.getKey();
            PathInfo<V, W> minPath = minEntry.getValue();
            selectedPaths.put(minVertex.value, minPath);
            // 移除
            paths.remove(minVertex);
            // 松弛操作
            for (Edge outEdge : minVertex.outEdges) {
                // 若outEdge.to已经离开桌面，则无需再进行松弛操作
                if (selectedPaths.containsKey(outEdge.to.value) || outEdge.to.equals(beginVertex)) continue;

                // 松弛操作
                relax(outEdge, minPath, paths);
            }
        }
        return selectedPaths;
    }

    /**
     * 从paths中获取最短的路径键值对
     */
    private Map.Entry<Vertex, W> getMinPath(Map<Vertex, W> paths) {
        Iterator<Map.Entry<Vertex, W>> iterator = paths.entrySet().iterator();
        Map.Entry<Vertex, W> minEntry = iterator.next();
        while (iterator.hasNext()) {
            Map.Entry<Vertex, W> entry = iterator.next();
            if (weightManager.compare(entry.getValue(), minEntry.getValue()) > 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

    /**
     * 从paths中获取最短的路径键值对
     */
    private Map.Entry<Vertex, PathInfo<V, W>> getMinPathInfo(Map<Vertex, PathInfo<V, W>> paths) {
        Iterator<Map.Entry<Vertex, PathInfo<V, W>>> iterator = paths.entrySet().iterator();
        Map.Entry<Vertex, PathInfo<V, W>> minEntry = iterator.next();
        while (iterator.hasNext()) {
            Map.Entry<Vertex, PathInfo<V, W>> entry = iterator.next();
            if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) > 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }

    /**
     * 松弛操作
     *
     * @param outEdge 需要松弛的边
     * @param minPath edge的from的最短路径
     * @param paths   存放其他没有离开桌面的点的最短路径信息
     */
    private void relax(Edge outEdge, PathInfo<V, W> minPath, Map<Vertex, PathInfo<V, W>> paths) {
        // 目前计算的最短路径
        W newWeight = weightManager.add(minPath.weight, outEdge.weight);
        // 之前的最短路径
        PathInfo<V, W> oldPath = paths.get(outEdge.to);
        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) <= 0) return;

        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(outEdge.to, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }

        oldPath.weight = newWeight;
        oldPath.edgeInfos.addAll(minPath.edgeInfos);
        oldPath.edgeInfos.add(outEdge.info());
    }

    @Override
    public void print() {
        vertices.forEach((k, v) -> {
            System.out.println(k + " => " + v.outEdges + " | " + v.inEdges);
        });

        edges.forEach(System.out::println);

        System.out.println();
    }
}
